//
//  Solution31.swift
//  swiftDemo
//
//  Created by JIENING ZHANG on 2022/11/18.
//  Copyright © 2022 lovivid. All rights reserved.
//

import UIKit

/*
整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

 

示例 1：

输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：

输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

 提示：

 1 <= nums.length <= 100
 0 <= nums[i] <= 100

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/next-permutation
// */

class Solution31: NSObject {
    func nextPermutation(_ nums: inout [Int]) {
        /*

        以下面排列为例子
        1,5,3,9,5,1
         
            先找出最后两个数字
            iTail[1]=1 // 从尾到头 第一个
            iTail[2]=5 // 从尾到头 第二个
            if iTail[1] > iTail[2]
            {
                交换 iTail[1] iTail[2]
                return
            }
            last2 min=1 max=5
            
            iTail[3]=9 > max
            last3 min=1 max=9
            
            iTail[4]=3 < max
            {
                last3 中找出比iTail[4]=3大的最小值，iTail[2]=5

                交换 iTail[4] iTail[2]
                数字排序为
                1,5,5,9,3,1

                last3 升序排序
                数字排序为
                1,5,5,1,3,9
            }

        // */
        

        if nums.count < 2 {
            return;
        }
        if nums.count == 2 {
            let tmp = nums[0];
            nums[0] = nums[1];
            nums[1] = tmp;
            return;
        }
        
        let inputArrLen = nums.count;
        if nums[inputArrLen-2] < nums[inputArrLen-1] {
            // 倒数第一数值 比 倒数第二数值大，交换后返回即可
            let tmp = nums[inputArrLen-2];
            nums[inputArrLen-2] = nums[inputArrLen-1];
            nums[inputArrLen-1] = tmp;
            return;
        }
        
        var lastK:Int = 2;
        var lastKMax:Int = nums[inputArrLen-2];
        
        var findLastK2Modify = false;
        lastK += 1;
        while lastK <= inputArrLen {
            if nums[inputArrLen-lastK] < lastKMax {
                // 倒数第k个数的数值 小于 lastKMax
                findLastK2Modify = true;
                break;
            }
            
            lastKMax = nums[inputArrLen-lastK];
            lastK += 1;
        }
        
        if findLastK2Modify {
            //在 [lastK+1 ... inputArrLen-1] 下标范围中找出比iTail[4]=3大的，却是最小值
            var swapIndex = -1;
            for index in inputArrLen-lastK+1 ... inputArrLen-1 {
                if nums[index] > nums[inputArrLen-lastK] {
                    if swapIndex < 0 {
                        // 第一个 比 iTail[lastK] 大 的 index 赋值给 swapIndex
                        swapIndex = index;
                    } else if nums[index] < nums[swapIndex] {
                        // 比 iTail[lastK] 大，但是比 之前找到的小
                        swapIndex = index;
                    }
                }
            }
            
            // lastK 和 swapIndex 交换
            let tmp = nums[inputArrLen-lastK];
            nums[inputArrLen-lastK] = nums[swapIndex];
            nums[swapIndex] = tmp;
            
            // 冒泡 升序排序 lastK+1 ... inputArrLen-1
            for upEnd in stride(from: inputArrLen-1, to: inputArrLen-lastK, by: -1) {
                for inner in inputArrLen-lastK+1 ..< upEnd {
                    if nums[inner] > nums[inner+1] {
                        let tmp = nums[inner];
                        nums[inner] = nums[inner+1];
                        nums[inner+1] = tmp;
                    }
                }
            }
            
            
        } else {
            // 这时，整个数组nums是倒序排序的，翻转一下，使得nums变成升序排序
            nums.sort();
        }
        
    }
}
